{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tallest Billboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tallestBillboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最高的广告牌"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。</p>\n",
    "\n",
    "<p>你有一堆可以焊接在一起的钢筋 <code>rods</code>。举个例子，如果钢筋的长度为 <code>1</code>、<code>2</code> 和 <code>3</code>，则可以将它们焊接在一起形成长度为 <code>6</code>&nbsp;的支架。</p>\n",
    "\n",
    "<p>返回 <em>广告牌的最大可能安装高度</em> 。如果没法安装广告牌，请返回 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,2,3,6]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,2,3,4,5,6]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,2]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没法安装广告牌，所以返回 0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>0 &lt;= rods.length &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= rods[i] &lt;= 1000</code></li>\n",
    "\t<li><code>sum(rods[i]) &lt;= 5000</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tallest-billboard](https://leetcode.cn/problems/tallest-billboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tallest-billboard](https://leetcode.cn/problems/tallest-billboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,6]', '[1,2,3,4,5,6]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        sm = sum(rods) // 2\n",
    "        has = [float(\"-inf\")] * (2*sm+1)\n",
    "        has[sm] = 0\n",
    "        for i in rods:\n",
    "            nhas = has[:]\n",
    "            for j in range(2*sm+1):\n",
    "                if j - i >= 0 and has[j-i] + i > nhas[j]:\n",
    "                    nhas[j] = has[j-i] + i\n",
    "                if j + i <= 2 * sm and has[j+i] + i > nhas[j]:\n",
    "                    nhas[j] = has[j+i] + i\n",
    "            has = nhas\n",
    "            # print(has)\n",
    "        return has[sm] // 2 if has[sm] != float(\"-inf\") else -1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        sm = sum(rods) // 2\n",
    "        has = [float(\"-inf\")] * (2*sm+1)\n",
    "        has[sm] = 0\n",
    "        nsm = sm\n",
    "        for i in rods:\n",
    "            nsm = max(nsm - i, 0)\n",
    "            nhas = has[:]\n",
    "            for j in range(nsm, 2*sm+1-nsm):\n",
    "                if j - i >= 0 and has[j-i] + i > nhas[j]: nhas[j] = has[j-i] + i\n",
    "                if j + i <= 2 * sm and has[j+i] + i > nhas[j]: nhas[j] = has[j+i] + i\n",
    "            has = nhas\n",
    "        return has[sm] // 2\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        s = sum(rods)\n",
    "        dp = [-1] * (s + 1)\n",
    "        dp[0] = 0\n",
    "        for rod in rods:\n",
    "            curr = dp.copy()\n",
    "            for h in range(s + 1):\n",
    "                if curr[h] < 0:\n",
    "                    continue\n",
    "                dp[h + rod] = max(dp[h + rod], curr[h])\n",
    "                dp[abs(h - rod)] = max(dp[abs(h - rod)], curr[h] + min(h, rod))\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        sm = sum(rods) // 2\n",
    "        has = [float(\"-inf\")] * (2*sm+1)\n",
    "        has[sm] = 0\n",
    "        for i in rods:\n",
    "            nhas = has[:]\n",
    "            for j in range(2*sm+1):\n",
    "                if j - i >= 0 and has[j-i] + i > nhas[j]: nhas[j] = has[j-i] + i\n",
    "                if j + i <= 2 * sm and has[j+i] + i > nhas[j]: nhas[j] = has[j+i] + i\n",
    "            has = nhas\n",
    "        return has[sm] // 2\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def tallestBillboard(self,rods:List[int])->int:\n",
    "    INF=0x3f3f3f3f\n",
    "    n=len(rods)\n",
    "    s=sum(rods)\n",
    "    dp=[-INF]*(s+1)\n",
    "    dp[0]=0\n",
    "    for i in range(1,n+1):\n",
    "      ndp=copy.deepcopy(dp)\n",
    "      for j in range(0,s+1):\n",
    "        if j+rods[i-1]<=s and dp[j]>=j:  \n",
    "          ndp[j+rods[i-1]]=max(dp[j]+rods[i-1],ndp[j+rods[i-1]])\n",
    "        if rods[i-1]<=j:\n",
    "          ndp[j-rods[i-1]]=max(dp[j],ndp[j-rods[i-1]])\n",
    "        elif rods[i-1]>j and dp[j]>=j:\n",
    "          ndp[rods[i-1]-j]=max(ndp[rods[i-1]-j],dp[j]+rods[i-1]-j)\n",
    "      dp=copy.deepcopy(ndp)\n",
    "    return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def tallestBillboard(self,rods:List[int])->int:\n",
    "    INF=0x3f3f3f3f\n",
    "    n=len(rods)\n",
    "    s=sum(rods)\n",
    "    dp=[-INF]*(s+1)\n",
    "    dp[0]=0\n",
    "    for i in range(1,n+1):\n",
    "      ndp=copy.deepcopy(dp)\n",
    "      for j in range(0,s+1):\n",
    "        if j+rods[i-1]<=s:  \n",
    "          ndp[j+rods[i-1]]=max(dp[j]+rods[i-1],ndp[j+rods[i-1]])\n",
    "        if rods[i-1]<=j:\n",
    "          ndp[j-rods[i-1]]=max(dp[j],ndp[j-rods[i-1]])\n",
    "        else:\n",
    "          ndp[rods[i-1]-j]=max(ndp[rods[i-1]-j],dp[j]+rods[i-1]-j)\n",
    "      dp=copy.deepcopy(ndp)\n",
    "    return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "    # 使用一个字典来记录可能的高度差以及对应的最高支架高度\n",
    "        dp = {0: 0}\n",
    "\n",
    "        for rod in rods:\n",
    "            # 创建一个新的字典来保存更新后的状态\n",
    "            new_dp = dp.copy()\n",
    "\n",
    "            # 遍历当前的状态\n",
    "            for diff, height in dp.items():\n",
    "                # 不使用当前钢筋\n",
    "                new_dp[diff] = max(new_dp.get(diff, 0), height)\n",
    "\n",
    "                # 放在左侧\n",
    "                new_dp[diff + rod] = max(new_dp.get(diff + rod, 0), height)\n",
    "\n",
    "                # 放在右侧\n",
    "                new_dp[abs(diff - rod)] = max(new_dp.get(abs(diff - rod), 0), height + min(rod, diff))\n",
    "\n",
    "            dp = new_dp\n",
    "\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0:\n",
    "        #         return 0 if j == 0 else -inf\n",
    "        #     return max(dfs(i - 1,j),\n",
    "        #     dfs(i - 1,j - rods[i]),dfs(i - 1,j + rods[i]) + rods[i])\n",
    "\n",
    "        # return max(0,dfs(n - 1,0))\n",
    "\n",
    "        # m = sum(rods)\n",
    "        # f = [[-inf]*(2*m + 1) for _ in range(n + 1)]\n",
    "        # # [-m,-1] + 0 +[1,m]\n",
    "        # # [0,m - 1] + [m] + [m + 1,2m]\n",
    "        # f[0][m] = 0\n",
    "        # for i,x in enumerate(rods):\n",
    "        #     for j in range(2*m + 1):\n",
    "        #         f[i + 1][j] = f[i][j]\n",
    "        #         if j + x <= 2*m:\n",
    "        #             f[i + 1][j] = max(f[i + 1][j],f[i][j + x] + x)\n",
    "        #         if j - x >= 0:\n",
    "        #             f[i + 1][j] = max(f[i + 1][j],f[i][j - x])\n",
    "        \n",
    "        # return max(0,f[-1][m])\n",
    "\n",
    "\n",
    "        m = sum(rods)\n",
    "        f = [-inf]*(2*m + 1)\n",
    "        # [-m,-1] + 0 +[1,m]\n",
    "        # [0,m - 1] + [m] + [m + 1,2m]\n",
    "        f[m] = 0\n",
    "        for i,x in enumerate(rods):\n",
    "            t = f[:]\n",
    "            for j in range(2*m + 1):\n",
    "                if j + x <= 2*m:\n",
    "                    t[j] = max(t[j],f[j + x] + x)\n",
    "                if j - x >= 0:\n",
    "                    t[j] = max(t[j],f[j - x])\n",
    "            f = t\n",
    "        \n",
    "        return max(0,f[m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        # dp = collections.defaultdict(int)\n",
    "        # # key: 总和 value: 正整数和， 每一个数字都可以乘以1，-1, 0 然后求总和为0的最大正数和 dp[0]\n",
    "        # dp[0] = 0\n",
    "\n",
    "        # for rod in rods:\n",
    "        #     for k, v in list(dp.items()):\n",
    "        #         dp[k + rod] = max(dp[k + rod], v + rod)\n",
    "        #         dp[k - rod] = max(dp[k - rod], v)\n",
    "\n",
    "        # return dp[0]\n",
    "    \n",
    "\n",
    "        # 折半搜索\n",
    "        n = len(rods)\n",
    "        # 和 正数和\n",
    "        dic1 = collections.defaultdict(int)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(l, r, sum, positive, dic):\n",
    "            if l == r:\n",
    "                dic[sum] = max(dic[sum], positive)\n",
    "                return\n",
    "\n",
    "            dfs(l+1, r, sum, positive, dic)\n",
    "            dfs(l+1, r, sum + rods[l], positive + rods[l], dic)\n",
    "            dfs(l+1, r, sum - rods[l], positive, dic)\n",
    "\n",
    "\n",
    "        dfs(0, n//2, 0, 0, dic1)\n",
    "        dfs(n//2, n, 0, 0, dic2)\n",
    "\n",
    "        ans = 0\n",
    "        for k1, v1 in dic1.items():\n",
    "            if -k1 in dic2:\n",
    "                ans = max(ans, v1 + dic2[-k1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def tallestBillboard(self,rods:List[int])->int:\n",
    "    INF=0x3f3f3f3f\n",
    "    n=len(rods)\n",
    "    s=sum(rods)\n",
    "    dp=[-INF]*(s+1)\n",
    "    dp[0]=0\n",
    "    for i in range(1,n+1):\n",
    "      ndp=copy.deepcopy(dp)\n",
    "      for j in range(0,s+1):\n",
    "        if j+rods[i-1]<=s:  \n",
    "          ndp[j+rods[i-1]]=max(dp[j]+rods[i-1],ndp[j+rods[i-1]])\n",
    "        if rods[i-1]<=j:\n",
    "          ndp[j-rods[i-1]]=max(dp[j],ndp[j-rods[i-1]])\n",
    "        else:\n",
    "          ndp[rods[i-1]-j]=max(ndp[rods[i-1]-j],dp[j]+rods[i-1]-j)\n",
    "      dp=copy.deepcopy(ndp)\n",
    "    return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp = {0: 0}\n",
    "        for d in rods:\n",
    "            for k, v in list(dp.items()):\n",
    "                dp[k + d] = max(dp.get(k + d, 0), v)\n",
    "                dp[abs(k - d)] = max(dp.get(abs(k - d), 0), v + min(k, d))\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp = {0: 0}\n",
    "        for rod in rods:\n",
    "            for k, v in dp.copy().items():\n",
    "                d = k + rod\n",
    "                h = v + rod\n",
    "                if d not in dp or h > dp[d]:\n",
    "                    dp[d] = h\n",
    "                h1, h2 = v, v - k + rod\n",
    "                h = max(h1, h2)\n",
    "                d = h - min(h1, h2)\n",
    "                if d not in dp or h > dp[d]:\n",
    "                    dp[d] = h\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        rods.sort()\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = 0\n",
    "        for x in rods:\n",
    "            for d,y in list(dp.items()):\n",
    "                dp[d+x] = max(dp[d+x],y+x)\n",
    "                dp[abs(d-x)] = max(x+y-d,y,dp[abs(d-x)])\n",
    "            #print(dp)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef tallestBillboard(self,rods:List[int])->int:\n",
    "\t\tn=len(rods)\n",
    "\t\tif n<=1:return 0\n",
    "\t\ts=sum(rods)\n",
    "\t\tdp=[[-1 for _ in range(s+1)] for _ in range(n)]\n",
    "\t\tdp[0][rods[0]]=dp[0][0]=0\n",
    "\t\tfor i in range(1,n):\n",
    "\t\t\tfor j in range(0,s+1):\n",
    "\t\t\t\tif dp[i-1][j]==-1:\t#上一行状态不存在\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tdp[i][j]=max(dp[i][j],dp[i-1][j]);  #当前钢筋不要\n",
    "\t\t\t\tdp[i][j+rods[i]]=max(dp[i][j+rods[i]],dp[i-1][j]);  #当前钢筋加在长的一边\n",
    "\t\t\t\tdp[i][abs(j-rods[i])]=max(dp[i][abs(j-rods[i])],dp[i-1][j]+min(j,rods[i])) #当前钢筋加在短的一边，高度差为abs(j-rods[i])\n",
    "\t\treturn 0 if dp[n-1][0]==-1 else dp[n-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef tallestBillboard(self, rods: List[int]) -> int:\n",
    "\t\tn=len(rods)\n",
    "\t\tif n<=1:return 0\n",
    "\t\ts=sum(rods)\n",
    "\t\tdp=[[-1 for _ in range(s+1)] for _ in range(n)]\n",
    "\t\tdp[0][rods[0]]=dp[0][0]=0\n",
    "\t\tfor i in range(1,n):\n",
    "\t\t\tfor j in range(0,s+1):\n",
    "\t\t\t\tif dp[i-1][j]==-1:\t#上一行状态不存在\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tdp[i][j]=max(dp[i][j],dp[i-1][j]);  #当前钢筋不要\n",
    "\t\t\t\tdp[i][j+rods[i]]=max(dp[i][j+rods[i]],dp[i-1][j]);  #当前钢筋加在长的一边\n",
    "\t\t\t\tdp[i][abs(j-rods[i])]=max(dp[i][abs(j-rods[i])],dp[i-1][j]+min(j,rods[i])) #当前钢筋加在短的一边，高度差为abs(j-rods[i])\n",
    "\t\treturn 0 if dp[n-1][0]==-1 else dp[n-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        pre[0] = 0\n",
    "        for num in rods:\n",
    "            cur = pre.copy()\n",
    "            for p in pre:\n",
    "                cur[p+num] = max(cur[p+num], pre[p])\n",
    "                cur[p - num] = max(cur[p - num], pre[p] + num)\n",
    "            pre = cur\n",
    "        return pre[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0 : 0}\n",
    "        for rod in rods:\n",
    "            new_dp = dp.copy()\n",
    "            for k, v in dp.items():\n",
    "                new_dp[k + rod] = max(new_dp.get(k + rod, 0), v + rod)\n",
    "                new_dp[k - rod] = max(new_dp.get(k - rod, 0), v)\n",
    "            dp = new_dp\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            for k, b in list(dp.items()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            for k, b in list(dp.items()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        pre=dict()\n",
    "        pre[0]=0\n",
    "        for rod in rods:\n",
    "            cur=pre.copy()\n",
    "            for k, b in pre.items():\n",
    "                cur[k+rod]=max(cur.get(k+rod,0),b+rod)\n",
    "                cur[k-rod]=max(cur.get(k-rod, 0),b)\n",
    "            pre=cur.copy()\n",
    "        return pre[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            for k, b in list(dp.items()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\n",
    "        return dp[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 在原有代码改一点就行了\r\n",
    "class Solution:\r\n",
    "    def tallestBillboard(self, rods):\r\n",
    "        dp = {0: 0}\r\n",
    "        for i in rods:\r\n",
    "            # 浅拷贝和深拷贝请看https://www.cnblogs.com/alimy/p/10374923.html\r\n",
    "            dp1 = dp.copy()\r\n",
    "            for k in list(dp1.keys()):\r\n",
    "                # 把这里的dp1改成了dp，那么获取的就是最新值啦~\r\n",
    "                dp[k + i] = max(dp.get(k + i, 0), dp1[k] + i)\r\n",
    "                dp[k - i] = max(dp.get(k - i, 0), dp1[k])\r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0 : 0}\n",
    "        for rod in rods:\n",
    "            for k, v in list(dp.items()):\n",
    "                dp[k + rod] = max(dp.get(k + rod, 0), v + rod)\n",
    "                dp[k - rod] = max(dp.get(k - rod, 0), v)\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            dp1 = dp.copy()\n",
    "            for k in list(dp1.keys()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), dp1[k] + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), dp1[k])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\r\n",
    "        \"\"\"\r\n",
    "        将问题转化为求数组和为0时的组合, \r\n",
    "        对任何一个数, 可以用三种方式对待它(乘以1, -1或0),\r\n",
    "        目标是求和为0时的最大的所有正数的和。\r\n",
    "        例如[1,2,3], 可以对1, 2乘以1, 3乘以-1, 此时和为0, 最大正数和为1+2=3。\r\n",
    "        用字典来存储每一步的结果, 键和值(k:v)分别是\"总和\"以及\"正数和\"。\r\n",
    "        https://leetcode.cn/problems/tallest-billboard/solutions/368725/yi-quan-ji-ben-mei-shuo-ming-bai-de-zhe-pian-kan-l/\r\n",
    "        \"\"\"\r\n",
    "        dp = {0: 0}\r\n",
    "        for rod in rods:\r\n",
    "            for k, v in list(dp.items()):\r\n",
    "                dp[k + rod] = max(dp.get(k + rod, 0), v + rod)\r\n",
    "                dp[k - rod] = max(dp.get(k - rod, 0), v)\r\n",
    "            \r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            for k, b in list(dp.items()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp={0:0}\n",
    "        for it in rods:\n",
    "            for a,b in list(dp.items()):\n",
    "                dp[a+it]=max(dp.get(a+it,0),it+b)\n",
    "                dp[a-it]=max(dp.get(a-it,0),b)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        # \n",
    "        dp = {0:0}\n",
    "        for i in range(len(rods)):\n",
    "            cur = rods[i]\n",
    "            for k,v in list(dp.items()):\n",
    "                dp[k+cur] = max(dp.get(k+cur, 0), v+cur)\n",
    "                dp[k-cur] = max(dp.get(k-cur, 0), v)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for rod in rods:\n",
    "            for k, v in list(dp.items()):\n",
    "                dp[k + rod] = max(dp[k + rod], v + rod)\n",
    "                dp[k - rod] = max(dp[k - rod], v)\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def tallestBillboard(self, rods):\r\n",
    "        dp = {0: 0}\r\n",
    "        for i in rods:\r\n",
    "            for k, b in list(dp.items()):\r\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\r\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\r\n",
    "        dp = {0: 0}\r\n",
    "        for rod in rods:\r\n",
    "            for k, v in list(dp.items()):\r\n",
    "                dp[k + rod] = max(dp.get(k + rod, 0), v + rod)\r\n",
    "                dp[k - rod] = max(dp.get(k - rod, 0), v)\r\n",
    "            \r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp = {0:0}\n",
    "        for i in range(len(rods)):\n",
    "            cur = rods[i]\n",
    "            for k,v in list(dp.items()):\n",
    "                dp[k+cur] = max(dp.get(k+cur, 0), v+cur)\n",
    "                dp[k-cur] = max(dp.get(k-cur, 0), v)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "\n",
    "        dp = collections.defaultdict(int)\n",
    "        dp[0] = 0\n",
    "        for rod in rods:\n",
    "            for score, positive in list(dp.items()):\n",
    "                dp[score+rod]= max(dp[score+rod], positive+rod) \n",
    "                dp[score-rod]= max(dp[score-rod], positive)\n",
    "       \n",
    "        return dp[0]         \n",
    "\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        d = {0:0}\n",
    "        for r in rods:\n",
    "            for k,v in list(d.items()):\n",
    "                d[k + r] = max(d.get(k+r, 0), v+r)\n",
    "                d[k - r] = max(d.get(k-r, 0), v)\n",
    "        \n",
    "        return d[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        # 每个钢筋都可以乘 1,0,-1 表示用在左边，不用，用在右边\n",
    "        # 那么问题就变成了组合的总和为0时，正数部分的最大值\n",
    "        # dp[k] = v 表示总和为k时，最大的正数和为v\n",
    "        # 初始时，dp = {0:0} 表示总和为0，正数和为0\n",
    "\n",
    "        dp = {0:0}\n",
    "        for i in range(len(rods)):\n",
    "            cur = rods[i]\n",
    "            for k,v in list(dp.items()):\n",
    "                dp[k+cur] = max(dp.get(k+cur, 0), v+cur)\n",
    "                dp[k-cur] = max(dp.get(k-cur, 0), v)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp = collections.defaultdict(int)\n",
    "        # key: 总和 value: 正整数和， 每一个数字都可以乘以1，-1, 0 然后求总和为0的最大正数和 dp[0]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for rod in rods:\n",
    "            for k, v in list(dp.items()):\n",
    "                dp[k + rod] = max(dp[k + rod], v + rod)\n",
    "                dp[k - rod] = max(dp[k - rod], v)\n",
    "\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            for k, b in list(dp.items()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        dp = collections.defaultdict(int)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for num in rods:\n",
    "            for k,v in list(dp.items()):\n",
    "                dp[k+num] = max([dp[k+num], v+num])\n",
    "                dp[k-num] = max([dp[k-num], v])\n",
    "        return(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        dp = {0: 0}\n",
    "        for i in rods:\n",
    "            for k, b in list(dp.items()):\n",
    "                dp[k + i] = max(dp.get(k + i, 0), b + i)\n",
    "                dp[k - i] = max(dp.get(k - i, 0), b)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        m = sum(rods)\n",
    "        # 以i为结尾，两面相差j的时候(左-右=j)，左边的最大值。如此，f[n - 1][0]即为答案。\n",
    "        # j的取值范围是【-m,m】把它映射到【0,2m】\n",
    "        f = [[-inf] * (2 * m + 1) for _ in range(n + 1)]\n",
    "        f[0][m] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m * 2 + 1):\n",
    "                x = rods[i - 1]\n",
    "                f[i][j] = f[i - 1][j]\n",
    "                if j - x > 0:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j - x] + x)\n",
    "                if j + x <= m * 2:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j + x])\n",
    "        return f[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        m = sum(rods)\n",
    "        # f[i][j] 从前i个中选择，高度差为j时，且左面较高时，左边的最大高度。\n",
    "        f = [[-inf] * (m * 2 + 1) for _ in range(n + 1)]\n",
    "        f[0][m] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m * 2 + 1):\n",
    "                x = rods[i - 1]\n",
    "                # 当前广告牌可以选择不接\n",
    "                f[i][j] = f[i - 1][j]\n",
    "                # 当前广告牌接在左边\n",
    "                if j - x > 0:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j - x] + x)\n",
    "                # 当前广告牌接在右面, 当前高度差j 比上一状态高度差小了x，\n",
    "                # 所以 上一状态的高度差 是j+x\n",
    "                if j + x <= m * 2:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j + x])\n",
    "        # print(f)\n",
    "        return f[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0:\n",
    "        #         return 0 if j == 0 else -inf\n",
    "        #     return max(dfs(i - 1,j + rods[i]) + rods[i],\n",
    "        #     dfs(i - 1,j - rods[i]) + rods[i],dfs(i - 1,j))\n",
    "\n",
    "        # return max(0,dfs(n - 1,0)//2)\n",
    "\n",
    "        m = sum(rods)\n",
    "        f = [[-inf]*(2*m + 1) for _ in range(n + 1)]\n",
    "        # [-m,-1] + 0 +[1,m]\n",
    "        # [0,m - 1] + [m] + [m + 1,2m]\n",
    "        f[0][m] = 0\n",
    "        for i,x in enumerate(rods):\n",
    "            for j in range(2*m + 1):\n",
    "                f[i + 1][j] = f[i][j]\n",
    "                if j + x <= 2*m:\n",
    "                    f[i + 1][j] = max(f[i + 1][j],f[i][j + x] + x)\n",
    "                if j - x >= 0:\n",
    "                    f[i + 1][j] = max(f[i + 1][j],f[i][j - x] + x)\n",
    "        \n",
    "        return max(0,f[-1][m] // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        f = []\n",
    "        \"\"\"\n",
    "        f[i][j] = f[i-1][j]\n",
    "        f[i][j+len] = f[i-1][j]\n",
    "        f[i][j-len] = f[i-1][j] + len\n",
    "        f[i][len - j] = f[i-1][j] + j\n",
    "        \"\"\"\n",
    "        r_sum = sum(rods)\n",
    "        for i in range(len(rods)+1):\n",
    "            f.append([-10 ** 9] * (r_sum+1))\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, len(rods)+1):\n",
    "            r_len = rods[i-1]\n",
    "            for j in range(r_sum+1):\n",
    "                f[i][j] = max(f[i-1][j], f[i][j])\n",
    "                if j + r_len < r_sum:\n",
    "                    f[i][j+r_len] = max(f[i-1][j], f[i][j+r_len])\n",
    "                if j >= r_len:\n",
    "                    f[i][j-r_len] = max(f[i-1][j] + r_len, f[i][j-r_len])\n",
    "                if j <= r_len:\n",
    "                    f[i][r_len - j] = max(f[i-1][j] + j, f[i][r_len - j])\n",
    "        result = 0\n",
    "\n",
    "        for i in range(len(rods)+1):\n",
    "\n",
    "            result = max(result, f[i][0])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        m = sum(rods)\n",
    "        f = [[-inf] * (m * 2 + 1) for _ in range(n + 1)]\n",
    "        f[0][m] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(m * 2 + 1):\n",
    "                x = rods[i - 1]\n",
    "                f[i][j] = f[i - 1][j]\n",
    "                if j - x > 0:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j - x] + x)\n",
    "                if j + x <= m * 2:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j + x])\n",
    "        return f[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        def check(tmp):\n",
    "            dct = dict()\n",
    "            n = len(tmp)\n",
    "            \n",
    "            def dfs(i):\n",
    "                nonlocal total, pos\n",
    "                if i == n:\n",
    "                    if pos > dct.get(total, -inf):\n",
    "                        dct[total] = pos\n",
    "                    return \n",
    "                for d in [-1, 0, 1]:\n",
    "                    total += d*tmp[i]\n",
    "                    pos += tmp[i] if d == 1 else 0\n",
    "                    dfs(i+1)\n",
    "                    total -= d * tmp[i]\n",
    "                    pos -= tmp[i] if d == 1 else 0\n",
    "                return \n",
    "            pos = total = 0\n",
    "            dfs(0)\n",
    "            return dct\n",
    "\n",
    "        m = len(rods)\n",
    "        pre = check(rods[:m//2])\n",
    "        post = check(rods[m//2:])\n",
    "        ans = 0\n",
    "        for k in pre:\n",
    "            if -k in post:\n",
    "                cur = pre[k] + post[-k]\n",
    "                ans = ans if ans > cur else cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 折半搜索\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        def make(A: List[int]) -> dict:\n",
    "            states = {(0, 0)}\n",
    "            for x in A:\n",
    "                states |= ({(a+x, b) for a, b in states} |\n",
    "                           {(a, b+x) for a, b in states})\n",
    "\n",
    "            delta = {}\n",
    "            for a, b in states:\n",
    "                delta[a-b] = max(delta.get(a-b, 0), a)\n",
    "            return delta\n",
    "\n",
    "        N = len(rods)\n",
    "        Ldelta = make(rods[:N//2])\n",
    "        Rdelta = make(rods[N//2:])\n",
    "\n",
    "        ans = 0\n",
    "        for d in Ldelta:\n",
    "            if -d in Rdelta:\n",
    "                ans = max(ans, Ldelta[d] + Rdelta[-d])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int: \n",
    "        self.rods = sorted(rods)\n",
    "        n = len(rods)\n",
    "        rv = self.dp(n-1, 0)\n",
    "        rv = max(rv,0)\n",
    "        return rv \n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dp(self, k, residual) -> int:\n",
    "        '''\n",
    "        select from top k rods\n",
    "        residual 表示当前 两边支架的差值\n",
    "        '''  \n",
    "        if residual==0:\n",
    "            rv = 0\n",
    "        else:\n",
    "            rv = -1\n",
    "        if k<0:\n",
    "            return rv \n",
    "        # 不使用这个钢筋\n",
    "        v = self.dp(k-1,residual)\n",
    "        rv = max(rv,v)\n",
    "        # 将这个钢筋，放到少的一侧\n",
    "        p = abs(residual-self.rods[k]) \n",
    "        v = self.dp(k-1, p)\n",
    "        if v>=0:\n",
    "            rv = max(rv, v+min(residual, self.rods[k])) \n",
    "        # 将这个钢筋，放到多的一侧\n",
    "        v =  self.dp(k-1, residual+self.rods[k]) \n",
    "        rv = max(rv,v)\n",
    "        return rv  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        @cache\n",
    "        def fun(now, sumnum):\n",
    "            if now == n:\n",
    "                return 0 if sumnum == 0 else -inf\n",
    "            return max(\n",
    "                fun(now+1, sumnum), \n",
    "                fun(now+1, sumnum - rods[now]), \n",
    "                rods[now] + fun(now+1, sumnum + rods[now])\n",
    "                )\n",
    "        return fun(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "        if len(rods) > 20:\n",
    "            return 0\n",
    "        else:\n",
    "            return dp(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        \"\"\" classic DFS-Memo / target sum \"\"\"\n",
    "\n",
    "        n = len(rods)\n",
    "        sum_ = sum(rods)\n",
    "        # dfs def: for current index of rods with the current sum cur, the max height\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, curr):\n",
    "            if i == n:\n",
    "                return 0 if curr == 0 else float('-inf')\n",
    "\n",
    "            S1 = dfs(i+1, curr)\n",
    "            S2 = dfs(i+1, curr - rods[i])\n",
    "            S3 = dfs(i+1, curr + rods[i]) + rods[i] \n",
    "\n",
    "            return max(S1, S2, S3)\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "        if len(rods) > 50:\n",
    "            return 0\n",
    "        else:\n",
    "            return dp(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, s):\n",
    "            if i == n:\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), \n",
    "                    dfs(i + 1, s - rods[i]), \n",
    "                    dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if i >= n:\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s - rods[i]), dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float(\"-inf\")\n",
    "            return max(dfs(i + 1,s),\n",
    "                       dfs(i + 1,s - rods[i]),\n",
    "                       dfs(i + 1,s + rods[i])+rods[i])\n",
    "        return dfs(0,0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s - rods[i]), dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        @functools.cache\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if i >= n:\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s - rods[i]), dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "\n",
    "        return dp(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "\n",
    "        return dp(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s - rods[i]), dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s - rods[i]), dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s - rods[i]), dfs(i + 1, s + rods[i]) + rods[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n=len(rods)\n",
    "        @cache\n",
    "        def dfs(i,now):\n",
    "            if i==n:\n",
    "                if now==0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -float(\"inf\")\n",
    "            ret=max(dfs(i+1,now),dfs(i+1,now-rods[i]),dfs(i+1,now+rods[i])+rods[i])\n",
    "            return ret\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i+1, s), dp(i+1, s-rods[i]), dp(i+1, s+rods[i]) + rods[i])\n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dfs(i + 1, s), dfs(i + 1, s + rods[i]), dfs(i + 1, s - rods[i]) + rods[i])\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods):\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == len(rods):\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(dp(i + 1, s),\n",
    "                       dp(i + 1, s - rods[i]),\n",
    "                       dp(i + 1, s + rods[i]) + rods[i])\n",
    "        print(rods)\n",
    "        return dp(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        n = len(rods)\n",
    "        @lru_cache(None)\n",
    "        def dp(i, s):\n",
    "            if i == n:\n",
    "                return 0 if s == 0 else float('-inf')\n",
    "            return max(\n",
    "                dp(i+1, s),\n",
    "                dp(i+1, s+rods[i])+rods[i],\n",
    "                dp(i+1, s-rods[i]))\n",
    "        return dp(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tallestBillboard(self, rods: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(rods):\n",
    "                return 0 if j == 0 else -inf\n",
    "            return max(dfs(i+1, j), dfs(i+1, j+rods[i]) + rods[i], dfs(i+1, j-rods[i]) + rods[i])\n",
    "        dfs.cache_clear()\n",
    "        return dfs(0, 0) // 2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
